package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/isomorphic-strings/description/?envType=study-plan-v2&envId=top-interview-150">同构字符串(Isomorphic Strings)</a>
 * <p>给定两个字符串 s 和 t ，判断它们是否是同构的。
 * <p>
 * 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
 * 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。</p>
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1:
 *      输入：s = "egg", t = "add"
 *      输出：true
 *
 * 示例 2：
 *      输入：s = "foo", t = "bar"
 *      输出：false
 *
 * 示例 3：
 *      输入：s = "paper", t = "title"
 *      输出：true
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= s.length <= 5 * 10^4</li>
 *     <li>t.length == s.length</li>
 *     <li>s 和 t 由任意有效的 ASCII 字符组成</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2022/5/19 14:10
 */
public class LC0205IsomorphicStrings_S {

    static class Solution {
        public boolean isIsomorphic(String s, String t) {
            // 如果长度不相等
            if (s.length() != t.length()) {
                return false;
            }
            Map<Character, Character> s2tMap = new HashMap<>();
            Map<Character, Character> t2sMap = new HashMap<>();
            int length = s.length();
            for (int i = 0; i < length; i++) {
                char sChar = s.charAt(i);
                char tChar = t.charAt(i);
                if (s2tMap.containsKey(sChar)) {
                    // 如果s->t的映射中，包含sChar，需要判断映射的字符t是否等于tChar。
                    // 如果等于，匹配成功；否则，匹配失败返回false。
                    if (s2tMap.get(sChar) != tChar) {
                        return false;
                    }
                } else {
                    // 如果s->t的映射中，不包含sChar，需判断t->s的映射中是否包含tChar
                    // 如果包含，说明当前tChar已经有映射，无法再与sChar建立映射，返回false
                    // 如果不包含，建立sChar->tChar与tChar->sChar的映射即可
                    if (t2sMap.containsKey(tChar)) {
                        return false;
                    }
                    s2tMap.put(sChar, tChar);
                    t2sMap.put(tChar, sChar);
                }
            }
            return true;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isIsomorphic("egg", "add"));
        System.out.println(solution.isIsomorphic("foo", "bar"));
        System.out.println(solution.isIsomorphic("paper", "title"));
        System.out.println(solution.isIsomorphic("hello", "worrd"));
        System.out.println(solution.isIsomorphic("baba", "bada"));
        System.out.println(solution.isIsomorphic("badc", "baba"));
    }
}
